class Solution:
    def putMarbles(self,weights, k):
        import sys
        n = len(weights)

    # 创建2D数组dp_min和dp_max，初始化为正无穷和负无穷
        dp_min = [[sys.maxsize] * (k + 1) for _ in range(n + 1)]
        dp_max = [[-sys.maxsize] * (k + 1) for _ in range(n + 1)]

    # 设置dp的base case：没有珠子的时候，分成 0 个背包，得分为0。
        dp_min[0][0] = 0
        dp_max[0][0] = 0

    # 前缀和数组，用于快速计算子数组的和
        prefix_sum = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix_sum[i] = prefix_sum[i - 1] + weights[i - 1]

    # 动态规划过程
        for i in range(1, n + 1):
            for j in range(1, min(i, k) + 1):
                for l in range(j - 1, i):
                    price = weights[l] + weights[i - 1]
                    if dp_min[l][j - 1] != sys.maxsize:  # 注意这里要确保dp_min[l][j - 1]有效
                        dp_min[i][j] = min(dp_min[i][j], dp_min[l][j - 1] + price)
                    if dp_max[l][j - 1] != -sys.maxsize:  # 同样确保dp_max[l][j - 1]有效
                        dp_max[i][j] = max(dp_max[i][j], dp_max[l][j - 1] + price)

    # 返回最大的差距
        return dp_max[n][k] - dp_min[n][k]

test = Solution()
weights=[1,3,5,1]
k=2
print(test.putMarbles(weights,k))